package org.basis.algorithm.list.practice;

import org.basis.algorithm.list.common.ListNodeUtil;
import org.basis.algorithm.list.common.SingleNode;

import java.util.PriorityQueue;

/**
 * 链表排序练习
 * <p>
 * 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * 【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整 数pivot。
 * 实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的 节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
 * <p>
 * 【进阶】在实现原问题功能的基础上增加如下的要求
 * 【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
 * 【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样
 * 【要求】调整后所有大于pivot的节点之间的相对顺序和调整前一样
 * 【要求】时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
 *
 * @author Mr_wenpan@163.com 2021/12/13 23:02
 */
public class ListSort2 {

    public static void main(String[] args) {
        SingleNode<Integer> head = ListNodeUtil.generateIntegerSingleList(20, 100, false);
        ListNodeUtil.printSingleList(head);
        SingleNode<Integer> newHead = sort1(head);
        ListNodeUtil.printSingleList(newHead);

        System.out.println();

        SingleNode<Integer> head2 = ListNodeUtil.generateIntegerSingleList(20, 100, false);
        ListNodeUtil.printSingleList(head2);
        SingleNode<Integer> newHead2 = sort2(head2);
        ListNodeUtil.printSingleList(newHead2);

        System.out.println();

        SingleNode<Integer> head3 = ListNodeUtil.generateIntegerSingleList(20, 100, false);
        ListNodeUtil.printSingleList(head3);
        SingleNode<Integer> newHead3 = listPartition(head3, 10);
        ListNodeUtil.printSingleList(newHead3);

    }

    /**
     * 通过优先级队列来实现排序
     */
    private static SingleNode<Integer> sort1(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        PriorityQueue<SingleNode<Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.data - o2.data);
        while (head != null) {
            queue.add(head);
            head = head.next;
        }

        // 从优先级队列中弹出时就有序了
        SingleNode<Integer> newHead = queue.poll();
        SingleNode<Integer> cur = newHead;
        while (!queue.isEmpty()) {
            SingleNode<Integer> poll = queue.poll();
            assert cur != null;
            cur.next = poll;
            cur = poll;
            poll.next = null;
        }

        return newHead;
    }

    /**
     * 自定义排序实现
     */
    private static SingleNode<Integer> sort2(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 插入排序实现
        SingleNode<Integer> cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }

        // 把链表节点加入到数组中
        cur = head;
        SingleNode<Integer>[] arr = new SingleNode[len];
        for (int i = 0; i < len; i++) {
            arr[i] = cur;
            cur = cur.next;
        }

        // 插入排序
        for (int i = 0; i < len; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j - 1].data > arr[j].data) {
                    swap(j, j - 1, arr);
                }
            }
        }

//        Arrays.sort(arr, (o1, o2) -> o1.data - o2.data);

        // 改变节点的指针关系
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i].next = arr[i + 1];
        }
        // 最后一个节点单独处理
        arr[arr.length - 1].next = null;

        return arr[0];
    }

    private static void swap(int i, int j, SingleNode<Integer>[] arr) {
        SingleNode<Integer> temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 链表分区方式三，时间复杂度为O(N)空间复杂度为O（1）
     */
    public static SingleNode<Integer> listPartition(SingleNode<Integer> head, int pivot) {

        if (head == null || head.next == null) {
            return head;
        }

        // 准备6个变量
        // 小于区的头尾节点
        SingleNode<Integer> sH = null;
        SingleNode<Integer> sT = null;
        // 等于区的头尾节点
        SingleNode<Integer> eH = null;
        SingleNode<Integer> eT = null;
        // 大于区的头尾节点
        SingleNode<Integer> mH = null;
        SingleNode<Integer> mT = null;

        // 遍历链表
        SingleNode<Integer> cur = head;
        while (cur != null) {

            // 暂存next节点
            SingleNode<Integer> next = cur.next;
            // 把当前节点的next指针置为空
            cur.next = null;

            if (cur.data > pivot) {
                if (mH == null) {
                    mH = cur;
                    mT = cur;
                } else {
                    mT.next = cur;
                    mT = cur;
                }
            } else if (cur.data < pivot) {
                if (sH == null) {
                    sH = cur;
                    sT = cur;
                } else {
                    sT.next = cur;
                    sT = cur;
                }
            } else {
                if (eH == null) {
                    eH = cur;
                    eT = cur;
                } else {
                    eT.next = cur;
                    eT = cur;
                }
            }
            cur = next;
        }

        // 串联三个链表
        if (sT != null) {
            sT.next = eH == null ? mH : eH;
        }
        if (eT != null) {
            eT.next = mH;
        }

        return sH;
    }

}
